1. Field of the Invention
The invention relates to data storage devices, and more particularly to flash memories.
2. Description of the Related Art
A data storage device, such as a memory card, stores data for a host. Generally, a data storage device comprises a storage medium and a controller. The storage medium is for data storage and may be a hard disk or a flash memory. The controller operates as an interface between the host and the storage medium, and transfers access commands sent from the host to the storage medium. When the host sends an access command to the controller, the host points out data to be accessed with a logical address. The storage medium, however, stores data according to physical addresses. The controller therefore must convert the logical address sent from the host to a physical address, and then sends the physical address to the storage medium, wherein the storage medium is requested to access data stored according to the physical address.
Generally, a controller converts a logical address to a physical address according to a link table. The link table stores a mapping relationship between logical and physical addresses. Because amount of data of the mapping relationship stored in the link table is large, the mapping relationship between the logical and physical addresses may be divided into mapping relationships of a plurality logical address ranges to be stored in a plurality of link tables. The link tables are stored in the storage medium. The data storage device comprises a random access memory for storing temporary data used by the controller. The random access memory has limited data capacity. Thus, the controller merely loads link tables, being currently used by the controller, from the storage medium to the random access memory.
For convenient searching, the link tables stored in the random access memory are often arranged to form a link list. Referring to FIG. 1, a schematic diagram of a plurality of link tables of a link list 100 stored in a random access memory is shown. The link list 100 comprises a start pointer 102 and a series of link tables 104˜110. The start pointer 102 points to a P-th link table 104 with a first order. A tail pointer of the P-th link table 104 is pointed to a Q-th link table 106 with a second order. The link tables 104˜110 of the link list 100 are therefore connected by tail pointers, and a last link table of the link list 100 is an X-th link table 110. The link tables 104˜110 of the link list 100 are the most recent link tables used by the controller. When the controller wants to convert a target logical address which is not stored in the link tables of the link list 100, the controller deletes the X-th link table 110 from the random access memory, reads a new link table comprising the target logical address from the storage medium, and stores the new link table in the random access memory as a component link table of the link list 100.
Referring to FIG. 2, a flowchart of a conventional data access method 200 of a storage medium is shown. A controller first receives a target logical address from a host (step 202). To determine whether a link list stored in a random access memory comprises a specific link table storing a mapping relationship of the target logical address, the controller must sequentially search a plurality of link tables of the link list for the target logical address. First, the controller obtains a first link table of the linked list as a target link table (step 204). The controller then checks whether a mapping relationship of the target logical address is stored in the target link table (step 206). If a mapping relationship of the target logical address is not stored in the target link table, the controller then determines a subsequent link table pointed out by a tail pointer of the target link table, and obtains the subsequent link table as the new target link table (step 210), and continues to check whether a mapping relationship of the target logical address is stored in the new target link table (step 206). Steps 206, 208, and 210 are repeatedly executing in a loop, until the controller finds the target link table storing the mapping relationship of the target logical address (step 206) or the link list does not comprise a subsequent link table of the target link table (step 208).
When the link list does not comprise a subsequent link table of the target link table (step 208), it is determined that the random access memory does not comprise the specific link table storing the mapping relationship of the target logical address. The controller then deletes a last link table of the link list from the random access memory (step 212), and then loads the specific link table storing the mapping relationship of the target logical address from the storage medium to the link list as the target link table (step 214). Thus, the random access memory now has a stored a target link table storing the mapping relationship of the target logical address. The controller then converts the target logical address to a target physical address according to the mapping relationship stored in the target link table (step 216), and then accesses data from the storage medium according to the target physical address (step 218). Finally, if the host sends a new access command to the data storage device (step 220), the controller performs steps 202˜218 again to convert a new target logical address of the new access command to a new target physical address and access data from the storage medium according to the new target physical address.
The conventional data access method 200 has shortcomings. When the controller receives a new target logical address, the controller must repeatedly execute steps 204˜210 in a loop to sequentially search all link tables of the link list for the new target logical address. Execution of the steps in a loop, however, requires a long time period and causes a delay in the data access process. For example, assume that a random access memory has a data capacity of 16 M Bytes, and a link table has stored mapping relationships with a data amount of 4K Bytes. The random access memory therefore stores almost 4K link tables, and the controller must search 4K link tables for the target logical address to determine whether the link tables stored in the random access memory comprises a mapping relationship of the target logical address, causing a long delay period and degrading performance of the data storage device. Thus, a data access method for efficiently determining whether a random access memory has stored a mapping relationship of a target logical address is required.